
#include "..\headers\ListOf.h"

#define MAXSIZE 100  // Assume the maximum length of the linear list is 100

// Assume the structure of the linear list is as follows
typedef struct {
  int data[MAXSIZE];
  int length;
} SqList;

// Initialize the linear list
void InitList(SqList &L) { L.length = 0; }

// Get the length of the linear list
int ListLength(SqList L) { return L.length; }

// Get the element at position i in the linear list
void GetElem(SqList L, int i, int &e) { e = L.data[i - 1]; }

// Insert an element into the linear list at position i
int ListInsert(SqList &L, int i, int e) {
  if (i < 1 || i > L.length + 1 || L.length == MAXSIZE)
    return 0;  // Insertion position is invalid or the list is full, insertion
               // failed
  for (int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1];
  L.data[i - 1] = e;
  L.length++;
  return 1;  // Insertion successful
}

// Merge two linear lists La and Lb into Lc
void MergeList(SqList La, SqList Lb, SqList &Lc) {
  InitList(Lc);
  int i = 0, j = 0, k = 0;
  int ai, bj;
  int La_len = ListLength(La);
  int Lb_len = ListLength(Lb);
  while (i < La_len && j < Lb_len) {  // Both La and Lb are not empty
    GetElem(La, i + 1, ai);
    GetElem(Lb, j + 1, bj);
    if (ai <= bj) {
      ListInsert(Lc, ++k, ai);
      i++;
    } else {
      ListInsert(Lc, ++k, bj);
      j++;
    }
  }
  while (i < La_len) {  // Insert the remaining elements in La into Lc
    GetElem(La, ++i, ai);
    ListInsert(Lc, ++k, ai);
  }
  while (j < Lb_len) {  // Insert the remaining elements in Lb into Lc
    GetElem(Lb, ++j, bj);
    ListInsert(Lc, ++k, bj);
  }
}

int main() {
  SqList La, Lb, Lc;
  int num1, num2;  // Length of La and Lb respectively

  // Input for La
  printf("Enter the length of linear list La: ");
  scanf("%d", &num1);
  InitList(La);
  for (int i = 0; i < num1; i++) {
    scanf("%d", &La.data[i]);
    La.length++;
  }

  // Input for Lb
  printf("Enter the length of linear list Lb: ");
  scanf("%d", &num2);
  InitList(Lb);
  for (int i = 0; i < num2; i++) {
    scanf("%d", &Lb.data[i]);
    Lb.length++;
  }
  if (La.length == 0 && Lb.length == 0) {
    printf("ERROR");
    return 0;
  }
  // Merge La and Lb into Lc
  MergeList(La, Lb, Lc);

  // Output the merged Lc
  printf("Merged linear list Lc:\n");
  for (int i = 0; i < Lc.length; i++) {
    printf("%d ", Lc.data[i]);
  }
  printf("\n");

  return 0;
}
